#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void dfs(int index, string &s, string &cur, vector<string> &ans, int cnt)
{
   // cout << cur << endl;
    if (cnt == 4 && index != s.size()) return;

    if (index == s.size()) {
	if (cnt == 4) 
	    ans.push_back(cur);
	//cout << endl;
	return;
    }
    if (cur.size() != 0) cur += '.';

    if (s[index] == '0') {
	string str = cur + '0';
	dfs(index+1, s, str, ans, cnt+1);
    } else {
	int num = 0;
	for (int i = index; i < index+3 && i < s.size(); i++) {
	    num = num*10 + s[i] - '0';
	    if (num > 255) return;
	    ostringstream ss;
	    ss << num; 	
	    string str = cur+ss.str();
	    dfs(i+1, s, str, ans, cnt+1);
	}
    }
}

//test on 1337 and pass all the test
    vector<string> restoreIpAddresses(string s) {
       vector<string> ans; 
	string cur;
	int cnt = 0;
	dfs(0, s, cur, ans, cnt);
	for (int i = 0; i < ans.size(); i++) 
	    cout << ans[i] << endl;
	return ans;
    }

//add better code
p(int index, const string &s, vector<string> &cur, vector<string> &ans)
{
    if (index == s.size()) {
        if (cur.size() == 4) { 
            string str = cur[0] + '.' + cur[1] + '.' + cur[2] + '.' + cur[3];
            ans.push_back(str);
        }    
        return;
    }    

    if (cur.size() >= 4) return;
    int val = 0; 
    for (int i = index; i < s.size() && i < index+3; i++) {
        val = val*10 + s[i] - '0'; 
        if (val > 255 || (i!= index && s[index] == '0')) continue;
        cur.push_back(s.substr(index, i-index+1));
        dfsIp(i+1, s, cur, ans);
        cur.pop_back();
    }    
}

    vector<string> restoreIpAddresses(string s) { 
        vector<string> ans; 
        vector<string> cur; 
        dfsIp(0, s, cur, ans);
        return ans;
    }nt main(int argc, char **argv)
{
    restoreIpAddresses("010010");
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
